package org.laizili.solution.leetcode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * <a href="https://leetcode.cn/problems/construct-quad-tree/">427. 建立四叉树</a>
 * <p>
 * tags: 简单递归; 分治;
 */
public class Problem427 {
    // Definition for a QuadTree node.
    private static class Node {
        public boolean val;
        public boolean isLeaf;
        public Node topLeft;
        public Node topRight;
        public Node bottomLeft;
        public Node bottomRight;


        public Node() {
            this.val = false;
            this.isLeaf = false;
            this.topLeft = null;
            this.topRight = null;
            this.bottomLeft = null;
            this.bottomRight = null;
        }

        public Node(boolean val, boolean isLeaf) {
            this.val = val;
            this.isLeaf = isLeaf;
            this.topLeft = null;
            this.topRight = null;
            this.bottomLeft = null;
            this.bottomRight = null;
        }

        public Node(boolean val, boolean isLeaf, Node topLeft, Node topRight, Node bottomLeft, Node bottomRight) {
            this.val = val;
            this.isLeaf = isLeaf;
            this.topLeft = topLeft;
            this.topRight = topRight;
            this.bottomLeft = bottomLeft;
            this.bottomRight = bottomRight;
        }
    }

    private static class Solution {
        public Node construct(int[][] grid) {
            return construct0(grid, 0, grid.length - 1, 0, grid[0].length - 1);
        }

        // divide and conquer
        private Node construct0(int[][] grid, int up, int down, int left, int right) {
            if (left == right && up == down) {
                // 递归边界
                return new Node(grid[up][left] == 1, true);
            }
            // 子任务
            int midRow = (up + down) / 2;
            int midCol = (left + right) / 2;
            Node topLeft = construct0(grid, up, midRow, left, midCol);
            Node topRight = construct0(grid, up, midRow, midCol + 1, right);
            Node bottomLeft = construct0(grid, midRow + 1, down, left, midCol);
            Node bottomRight = construct0(grid, midRow + 1, down, midCol + 1, right);
            //叶子结点才能根据val相等来合并
            if ((topLeft.isLeaf && topRight.isLeaf && bottomLeft.isLeaf && bottomRight.isLeaf) &&
                    (topLeft.val == topRight.val && topRight.val == bottomLeft.val && bottomLeft.val == bottomRight.val)) {
                return new Node(topLeft.val, true);
            } else {
                return new Node(true, false, topLeft, topRight, bottomLeft, bottomRight);
            }
        }
    }

    // test case
    public static void main(String[] args) {

//        Node root = new Solution().construct(new int[][]{
//                {1, 1, 1, 1, 0, 0, 0, 0},
//                {1, 1, 1, 1, 0, 0, 0, 0},
//                {1, 1, 1, 1, 1, 1, 1, 1},
//                {1, 1, 1, 1, 1, 1, 1, 1},
//                {1, 1, 1, 1, 0, 0, 0, 0},
//                {1, 1, 1, 1, 0, 0, 0, 0},
//                {1, 1, 1, 1, 0, 0, 0, 0},
//                {1, 1, 1, 1, 0, 0, 0, 0}
//        });
//        Node root = new Solution().construct(new int[][]{
//                {1, 1, 0, 0},
//                {0, 0, 1, 1},
//                {1, 1, 0, 0},
//                {0, 0, 1, 1},
//        });
//        Node root = new Solution().construct(new int[][]{
//                {0}
//        });
        Node root = new Solution().construct(new int[][]{
                {1, 1, 0, 0},
                {1, 1, 0, 0},
                {0, 0, 1, 1},
                {0, 0, 1, 1}
        });
        List<List<Integer>> res = new ArrayList<>();
        traverse(root, res);
        System.out.println(res);
    }

    private static void traverse(Node root, List<List<Integer>> res) {
        if (root != null) {
            Deque<Node> nodes = new ArrayDeque<>();
            nodes.add(root);
            while (!nodes.isEmpty()) {
                Node node = nodes.poll();
                if (node.isLeaf) {
                    res.add(List.of(1, node.val ? 1 : 0));
                } else {
                    nodes.add(node.topLeft);
                    nodes.add(node.topRight);
                    nodes.add(node.bottomLeft);
                    nodes.add(node.bottomRight);
                    res.add(List.of(0, node.val ? 1 : 0));
                }
            }
        }
    }
}
